package com.hspedu.newData.dmsxl.树.二叉树路径.路径;

import com.hspedu.newData.dmsxl.ds.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-26 
 * @Version: 1.0
 */

// 和560差不多，560是数组上，437是在二叉树上
public class LC437路径总和Ⅲ {

    public int pathSum(TreeNode root, int targetSum) {

        Map<Long,Long> map = new HashMap<>();
        map.put(0l,1l);
        int res = dfs(root, map, 0l, targetSum);
        return res;
    }

    // 还需要回溯
    public int dfs(TreeNode root, Map<Long,Long> map,long prev,long targetSum){
        if (root == null){
            return 0;
        }

        int ret = 0;
        prev += root.val;

        ret += map.getOrDefault(prev-targetSum,0l);
        map.put(prev,map.getOrDefault(prev,0l)+1);
        ret += dfs(root.left,map,prev,targetSum)+dfs(root.right,map,prev,targetSum);
        map.put(prev,map.getOrDefault(prev,0l)-1);
        return ret;
    }

}
